#include <bits/stdc++.h>
using namespace std;

/*
1935. 可以输入的最大单词数
已解答
简单
相关标签
premium lock icon
相关企业
提示
键盘出现了一些故障，有些字母键无法正常工作。而键盘上所有其他键都能够正常工作。

给你一个由若干单词组成的字符串 text ，单词间由单个空格组成（不含前导和尾随空格）；另有一个字符串 brokenLetters ，由所有已损坏的不同字母键组成，返回你可以使用此键盘完全输入的 text 中单词的数目。

 

示例 1：

输入：text = "hello world", brokenLetters = "ad"
输出：1
解释：无法输入 "world" ，因为字母键 'd' 已损坏。
示例 2：

输入：text = "leet code", brokenLetters = "lt"
输出：1
解释：无法输入 "leet" ，因为字母键 'l' 和 't' 已损坏。
示例 3：

输入：text = "leet code", brokenLetters = "e"
输出：0
解释：无法输入任何单词，因为字母键 'e' 已损坏。
 

提示：

1 <= text.length <= 104
0 <= brokenLetters.length <= 26
text 由若干用单个空格分隔的单词组成，且不含任何前导和尾随空格
每个单词仅由小写英文字母组成
brokenLetters 由 互不相同 的小写英文字母组成
*/

// 法一
class Solution {
public:
    int canBeTypedWords(string text, string brokenLetters) {
        // 损坏字母存入哈希 O(1)
        unordered_set<char> brokenSet(brokenLetters.begin(), brokenLetters.end());

        int cnt = 0, start = 0, n = text.size();

        // 遍历text 按空格分割单词 检查
        for (int i = 0; i <= n; i++) {
            // 遇到空格 遍历到字符串末尾
            if (i == n || text[i] == ' ') {
                // 截取当前单词
                string word = text.substr(start, i - start);
                // 检查单词是否不含损坏字母
                bool cnaType = true;
                for (char c : word) {
                    if (brokenSet.count(c)) {
                        cnaType = false;
                        break;
                    }
                }
                if (cnaType)    cnt++;

                start = i + 1;      // 更新起始索引，准备处理下一个单词（跳过空格）
            }
        }
        return cnt;
    }
};

// 法二
class Solution {
public:
    int canBeTypedWords(string text, string brokenLetters) {
        // 用损坏字母初始化哈希集合，O(1)快速判断字符是否损坏
        unordered_set<char> broken(brokenLetters.begin(), brokenLetters.end());
        
        int validWordCount = 0;       // 统计可完整输入的单词总数
        bool isCurrentWordValid = true; // 标记当前正在处理的单词是否可完整输入（无损坏字母）
        
        for (char ch : text) {
            if (ch == ' ') {          // 遇到空格，说明当前单词结束
                if (isCurrentWordValid) { // 若当前单词有效，计数+1
                    validWordCount++;
                }
                isCurrentWordValid = true; // 重置标志，准备处理下一个单词
            } 
            // 若当前字符是损坏字母，且当前单词仍被认为有效，则标记为无效
            else if (isCurrentWordValid && broken.count(ch)) {
                isCurrentWordValid = false;
            }
        }
        
        // 处理最后一个单词（文本末尾无空格，需单独判断）
        if (isCurrentWordValid) {
            validWordCount++;
        }
        
        return validWordCount;
    }
};